public class Sort {

    private static void swap(int[] data, int lhs, int rhs) {
        int temp = data[lhs];
        data[lhs] = data[rhs];
        data[rhs] = temp;
    }

    public static void BubbleSort(int[] data) {
        boolean flag = true;
        for (int i = 0; i < data.length - 1 && flag; i++) {
            flag = false;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j] < data[j - 1]) {
                    swap(data, j, j - 1);
                    flag = true;
                }
            }
        }
    }

    public static void SelectSort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            int min = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[min]) {
                    min = j;
                }
            }
            if (min != i) {
                swap(data, i, min);
            }
        }
    }

    public static void InsertSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            if (data[i] < data[i - 1]) {
                int temp = data[i];
                int j = i - 1;
                while (j >= 0 && data[j] > temp) {
                    data[j + 1] = data[j];
                    j--;
                }
                data[j + 1] = temp;
            }
        }
    }

    //O(n^3/2)
    public static void ShellSort(int[] data) {
        int increment = data.length;
        do {
            increment = increment / 3 + 1;
            ShellPass(data, increment);
        } while (increment > 1);
    }

    //将数据分为d个跳跃的子数组并分别进行直接插入排序
    private static void ShellPass(int[] data, int d) {
        for (int i = d; i < data.length; i++) {
            if (data[i] < data[i - d]) {
                int temp = data[i];
                int j = i - d;
                while (j >= 0 && data[j] > temp) {
                    data[j + d] = data[j];
                    j -= d;
                }
                data[j + d] = temp;
            }
        }
    }

    public static void HeapSort(int[] data) {
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            HeapAdjust(data, i, data.length);
        }
        for (int i = data.length - 1; i > 0; i--) {
            swap(data, 0, i);
            HeapAdjust(data, 0, i);
        }
    }

    //data数组中[s,m)子数列中除了s位置的元素外，其他满足大顶堆
    //将[s,m)子数列调整为大顶堆
    private static void HeapAdjust(int[] data, int s, int m) {
        int temp = data[s];
        for (int j = 2 * s + 1; j < m; j = 2 * j + 1) {
            if (j < m - 1 && data[j] < data[j + 1]) {
                j++;
            }
            if (temp < data[j]) {
                data[s] = data[j];
                s = j;
            }
        }
        data[s] = temp;
    }

    public static void MergeSort(int[] data) {
        MSort(data, 0, data.length);
    }

    private static void MSort(int[] data, int s, int t) {
        if (s >= t - 1) return;
        int mid = (s + t) / 2;
        MSort(data, s, mid);
        MSort(data, mid, t);
        Merge(data, s, mid, t);
    }

    private static void Merge(int[] data, int i, int m, int n) {
        int[] temp = new int[n - i];
        int index = 0;
        int lhs = i;
        int rhs = m;
        while (lhs < m && rhs < n) {
            if (data[lhs] < data[rhs]) {
                temp[index++] = data[lhs++];
            } else {
                temp[index++] = data[rhs++];
            }
        }
        while (lhs < m) {
            temp[index++] = data[lhs++];
        }
        while (rhs < n) {
            temp[index++] = data[rhs++];
        }
        for (index = 0; index < temp.length; index++) {
            data[i++] = temp[index];
        }
    }

    private static int Partition(int[] data, int low, int high) {
        int pivotKey = data[low];
        while (low < high) {
            while (low < high && data[high] >= pivotKey) {
                high--;
            }
            swap(data, low, high);
            while (low < high && data[low] <= pivotKey) {
                low++;
            }
            swap(data, low, high);
        }
        return low;
    }

    private static void QSort(int[] data, int low, int high) {
        int pivot;
        if (low < high) {
            pivot = Partition(data, low, high);
            QSort(data, low, pivot - 1);
            QSort(data, pivot + 1, high);
        }
    }

    public static void QuickSort(int[] data) {
        QSort(data, 0, data.length - 1);
    }

}
















